#include <stack>
#include <cstdio>
#include <queue>
#define maxsize 100
#define INF 0x1fffffff;
using  namespace std;

/*
 * 给一个数组 ，和一个数 输出
 */
//输入
int a[maxsize];
int n, k;

//bool dfs(int i, int sum){
//    if(i == n){
//        return sum == k;
//    }
//    return dfs(i + 1, sum) || dfs(i + 1, sum + a[i]);
//}

/*
 * p33
 * 问题描述： 将每个坐标值是 'W'的 重置为 '.'， 并且所以与其直接或间接相连的坐标也置为'.'
 * 问题分解：将当前坐标置为'.', 并且对周围坐标执行该操作
 */
//输入
int N, M;
char field[maxsize][maxsize];
void dfs(int x, int y){
    field[x][y] = '.';
    for(int dx = -1; dx <= 1; dx++){
        for (int dy = -1; dy < 1; dy++) {
            int nx = x + dx, ny = y + dy;
            if(nx >= 0 && nx < N && ny >= 0 && ny < M && field[nx][ny] == 'W'){
                dfs(nx, ny);
            }
        }
    }
}

/*
 * P34 迷宫的最短路径
 * 问题建模： 1. 当前状态 -> 其他四个方向的状态 记录状态转移后的最短距离
 *           2. 忽略 墙壁/不在边界内的情况
 *           3.到达终点退出程序
 */
typedef pair<int, int> P;
//输入
char maze[maxsize][maxsize + 1]; //表示迷宫字符串的数组

int sx, sy;  //
int gx, gy;

int d[maxsize][maxsize];  //到各个位置最短距离的数组
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, -1};
int bfs(){
    queue<P> que;
    //将所有位置初始化为INF
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            d[i][j] = INF;
        }
    }
    //将其点加入队列并将这一地点的距离设为0
    que.push(P(sx, sy));
    d[sx][sy] = 0;
    //不断循环知道队列长度为0
    while (que.size()){
        //取元素
        P p = que.front(); que.pop();
        if(p.first == gx && p.second == gy){
            return d[gx][gy];
        }
        //四个方向上的循环
        for (int i = 0; i < 4; ++i) {
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if(0 <= nx && nx < N &&
               0 <= ny && ny < M &&
               maze[nx][ny] != '#' && d[nx][ny] == INF)
            for (int j = 0; j < 4; ++j) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second];
            }
        }
        return d[gx][gy];
    }
}



